class NumMatrix {
    int dp[][];
    public NumMatrix(int[][] matrix) {
        int rowLen = matrix.length;
        if (rowLen == 0) {
            return;
        }
        int colLen = matrix[0].length;
        dp = new int[rowLen][colLen];
        for (int i = 0; i < colLen; i++) {
            for (int j = 0; j < rowLen; j++) {
                if (i == 0 && j == 0) {
                    dp[j][i] = matrix[0][0];
                } else if (i == 0) {
                    dp[j][i] = dp[j - 1][i] + matrix[j][i];
                } else if (j == 0) {
                    dp[j][i] = dp[j][i - 1] + matrix[j][i];
                } else {
                    dp[j][i] = dp[j][i - 1] + dp[j - 1][i] + matrix[j][i] - dp[j - 1][i - 1];
                }

            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int nums = dp[row2][col2];
        int l = 0;
        int t = 0;
        int lt = 0;
        if (col1 > 0) {
            l = dp[row2][col1 - 1];
        }
        if (row1 > 0) {
            t = dp[row1 - 1][col2];
        }
        if (col1 > 0 && row1 > 0) {
            lt = dp[row1 - 1][col1 - 1];
        }
        return nums - l - t + lt;
    }
}


class NumMatrix {
    int[][] m;

    public NumMatrix(int[][] matrix) {
        m = matrix;
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int nums = 0;
        for (int i = row1; i <= row2; i++) {
            for (int j = col1; j <= col2; j++) {
                nums = nums + m[i][j];
            }
        }
        return nums;
    }
}